/*
 * Copyright 北京航空航天大学  @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.ds;

import java.util.HashMap;
import java.util.Map;

/**
 * <p>
 * 增加和单词搜索
 * 
 * 查询包含正则表达式
 * </p>
 * @author towan
 * @email tongwenzide@163.com
 * @time 2015年5月27日
 */
public class WordDictionary {
    class TrieNode {
        // Initialize your data structure here.
        boolean isWord;
        Map<Character,TrieNode> children;
        public TrieNode() {
            children  = new HashMap<>();
        }
    }
    private TrieNode root = new TrieNode();  
    
    public void addWord(String word) {  
        Map<Character, TrieNode> children = root.children;  
        for(int i=0; i<word.length(); i++) {  
            char c = word.charAt(i);  
            TrieNode t;  
            if(children.containsKey(c)) {  
                t = children.get(c);  
            } else {  
                t = new TrieNode();  
                children.put(c, t);  
            }  
            children = t.children;  
            if(i==word.length()-1) t.isWord=true;  
        }  
    }  
  
    public boolean search(String word) {  
        return searchNode(word, root);  
    }  
      
    public boolean searchNode(String word, TrieNode tn) {  
        if(tn==null) return false;  
        if(word.length() == 0 ) return tn.isWord;  
          
        Map<Character, TrieNode> children = tn.children;  
        TrieNode t = null;  
        char c = word.charAt(0);  
        if(c=='.') {  
            for(char key : children.keySet() ) {  
                if(searchNode(word.substring(1), children.get(key) )) return true;  
            }  
            return false;  
        } else if(!children.containsKey(c)) {  
            return false;  
        } else {  
            t = children.get(c);  
            return searchNode(word.substring(1), t);  
        }  
    }     
    public static void main(String[] args) {
      WordDictionary wordDictionary = new WordDictionary();
      wordDictionary.addWord("bad");
      wordDictionary.addWord("dad");
      wordDictionary.addWord("mad");
      System.out.println(wordDictionary.search("pad"));
      System.out.println(wordDictionary.search("bad"));
      System.out.println(wordDictionary.search(".ad"));
      System.out.println(wordDictionary.search("b.."));
    }
}

// Your WordDictionary object will be instantiated and called as such:
// WordDictionary wordDictionary = new WordDictionary();
// wordDictionary.addWord("word");
// wordDictionary.search("pattern");